#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1000000 + 1;
int isPrime[N];
int prime[N], pcnt;
int factor[1000];

int f(int n) {
    if (isPrime[n]) {
        return n - 1;
    }
    int fcnt = 0;
    int nn = n; //cache
    int ans = 0;
    for (int i = 0; i < pcnt; i++) {
        while (n % prime[i] == 0) {
            n /= prime[i];
            if (fcnt == 0 || factor[fcnt - 1] != prime[i]) {
                factor[fcnt++] = prime[i];
            }
        }
        if (isPrime[n] || n == 1) {
            if (n != 1) factor[fcnt++] = n;
            break;
        }
    }
    for (int i = 1; i < (1 << fcnt); i++) { // mask
        int multiple = 1;
        int bitCount = __builtin_popcount(i);
        for (int j = 0; j < fcnt; j++) {
            if (i & (1 << j)) {
                multiple *= factor[j];
            }
        }
        int multipleCount = nn / multiple - (nn % multiple);
        if (bitCount & 1) {
            ans += multipleCount;
        } else {
            ans -= multipleCount;
        }
    }
    return nn - ans;
}

int main()
{
    for (int i = 0; i < N; i++) isPrime[i] = 1;
    isPrime[0] = isPrime[1] = 0;
    for (int i = 2; i < N; i++) {
        if (isPrime[i]) {
            prime[pcnt++] = i;
            for (int j = i + i; j < N; j += i) {
                isPrime[j] = 0;
            }
        }
    }

    double ans = 0;
    for (int i = 4; i < N; i++) {
        int fi = f(i);
        double t = 1.0 * i / fi;
        if (t > ans) {
            ans = t;
            cout << i << ' ' << ans << endl;
        }
    }

    return 0;
}
